牛客周赛 Round 31

GPT 局，我是废物，基础完全不行

A 小红小紫替换

小红拿到了一个字符串，她发现这个字符串可能是她自己的名字"kou"，于是想将其替换成小紫的名字"yukari"。你能帮帮她吗？

int main() {
    string s;
    cin >> s;
    if (s == "kou") {
        cout << "yukari" << endl;
    } else {
        cout << s << endl;
    }
}

B 小红的因子数

小红拿到了一个正整数 $x(1\le x\le {10}^{13})$，她想知道 $x$ 有多少个不同的素因子，你能帮帮她吗？

void solve() {
	ll x;
	cin >> x;
    int count = 0;
    for (ll i = 2; i * i <= x; i++) {
        if (x % i == 0) {
            while (x % i == 0) {//为了不同
                x /= i;
            }
            count++;
        }
    }
    if (x > 1) {
        count++;
    }
    cout << count << '\n';
}

C 小红的字符串中值

小红定义一个长度为奇数的字符串的“中值”为中间那个字符。例如"kou"的中值是'o'。
现在小红拿到了一个字符串，她想知道某个字符是多少个子串的中值。你能帮帮她吗？

#define int long long
signed main() {
    int n;
    char ch;
    cin >> n >> ch;
    
    string s;
    cin >> s;
    
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == ch) {
            count += min(i + 1, n - i);//到左边和右边的较小值
        }
    }
    cout << count << endl;
}

D 小红数组操作

小红拿到了一个数组，初始数组为空，她希望你实现以下两种操作：

• $1xy$,将 $x$ 插在 $y$ 的右边保证此时数组中没有元素等于$x$，且数组中存在一个$y$。特殊的，如果将$x$ 插入在数组的最左边，则$y=0$
• $2x$,删除元素 $x$

请你在所有操作后输出整个数组。

unordered_map 的 find 函数查询平均是 $O(1)$

void solve() {
    int q;
    std::cin >> q;
    std::list<int> arr;
    std::unordered_map<int, std::list<int>::iterator> index;
    for (int i = 0; i < q; i++) {
        int op;
        std::cin >> op;
        if (op == 1) {
            int x, y;
            std::cin >> x >> y;
            if (y == 0) {
                arr.push_front(x);
                index[x] = arr.begin();
            } else {
                auto it = index.find(y);
                if (it != index.end()) {
                    auto new_it = arr.insert(next(it->second), x);
                    index[x] = new_it;
                }
            }
        } else if (op == 2) {
            int x;
            std::cin >> x;
            auto it = index.find(x);
            if (it != index.end()) {
                arr.erase(it->second);
                index.erase(it);
            }
        }
    }

    std::cout << arr.size() << '\n';
    for (auto val : arr) {
        std::cout << val << " ";
    }
    std::cout << '\n';
}

E 小红的子集取反

小红拿到了一个数组，她准备选择若干元素乘以 -1，使得最终所有元素的和为 0。小红想知道最少需要选择多少个元素？

Solution.

DP

#define N 40000
int i, j, k, n, m, t, res = -1;
bitset<80005> f[205];

int main() {
    ios::sync_with_stdio(0);
    f[0][N] = 1;
    cin >> n;
    for (i = 1;i <= n;i++) {
        cin >> k;
        for (j = n;j >= 0;j--) {
            if (k >= 0) {
                f[j] >>= k;
                if (j) f[j] |= (f[j - 1] << k);
            } else {
                f[j] <<= -k;
                if (j) f[j] |= (f[j - 1] >> -k);
            }
        }
    }
    for (i = 0;i <= n;i++)
	    if (f[i][N]) {
        res = i; break;
    }
    cout << res;
}

如果 ndp 中没有存储 $c+x$ 的值，则将其设置为 y；如果已经存在，则将其更新为 min (ndp[c + x], y)。

同样的方法用于 $c-x$，将其设置为 y + 1 或者更新为 min (ndp[c - x], y + 1)。

对于每一个读入的数据，都要与数组中的数相加或相减

dp[i][j] = min (dp[i - 1][j + arr[i]], dp[i - 1][j - arr[j]] + 1)

int main() {
    map<int, int> dp;
    int n;
    cin >> n;
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        map<int, int> ndp;
        for (auto [c, y] : dp) {
            if (!ndp.count(c + x)) ndp[c + x] = y;
            else ndp[c + x] = min(ndp[c + x], y);
            if (!ndp.count(c - x)) ndp[c - x] = y + 1;
            else ndp[c - x] = min(ndp[c - x], y + 1);
        }
        dp = ndp;
    }
    if (!dp.count(0)) cout << -1;
    else cout << dp[0];
}

x + y = s
x - y = 0 $\to y=\frac{s}{2}$
从集合中挑选最少的元素，使得恰好为 $S/2$ 即可.(待更 $\dots$) 等我系统学DP

F 小红的连续段

小红定义一个字符串的“连续段”数量为：相同字符的极长连续子串的数量。例如，“aabbaaa”共有 3 个连续段：“aa”+“bb”+“aaa”。

现在，小红希望你求出，长度为 $x+y$，包含恰好有 $x$ 个'a'和 $y$ 个'b' 组成的字符串，连续段数量恰好为 $i$ 的字符串数量。你需要回答 $i\in [1,x+y]$ 的每个 $i$ 的答案。

Solution

组合+乘法原理

(待更 $\dots$)(看不懂 $\dots$)

long long modinv(long long a, long long m) {
    long long m0 = m, t, q;
    long long x0 = 0, x1 = 1;

    if (m == 1) {
        return 0;
    }
    
    // Apply extended Euclid Algorithm
    while (a > 1) {
        q = a / m;
        t = m;
        m = a % m, a = t;
        t = x0;
        x0 = x1 - q * x0;
        x1 = t;
    }
    
    if (x1 < 0) {
        x1 += m0;
    }
    
    return x1;
}
void solve() {
	int x, y;
    cin >> x >> y;

    int n = x + y;
    long long mod = 1e9 + 7;
    vector<long long> fac(n + 1);
    fac[0] = 1;
    for (int i = 1; i <= n; i++) {
        fac[i] = fac[i - 1] * i % mod;
    }
    vector<long long> inv(n + 1);
    inv[n] = modinv(fac[n], mod);
    for (int i = n - 1; i >= 0; i--) {
        inv[i] = inv[i + 1] * (i + 1) % mod;
    }

    vector<long long> res;
    for (int i = 1; i <= n; i++) {
        long long tmp = 0;
        if (i % 2 == 1) {
            int a = i / 2 + 1;
            int b = i / 2;

            if (a <= x && a >= 1 && b <= y && b >= 1) {
                long long r1 = fac[x - 1] * inv[a - 1] % mod * inv[x - a] % mod;
                long long r2 = fac[y - 1] * inv[b - 1] % mod * inv[y - b] % mod;
                tmp += r1 * r2 % mod;
                tmp %= mod;
            }
            if (a <= y && a >= 1 && b <= x && b >= 1) {
                long long r1 = fac[y - 1] * inv[a - 1] % mod * inv[y - a] % mod;
                long long r2 = fac[x - 1] * inv[b - 1] % mod * inv[x - b] % mod;
                tmp += r1 * r2 % mod;
                tmp %= mod;
            }
            res.push_back(tmp);
        } else {
            int a = i / 2;
            if (a <= x && a >= 1 && a <= y) {
                long long r1 = fac[x - 1] * inv[a - 1] % mod * inv[x - a] % mod;
                long long r2 = fac[y - 1] * inv[a - 1] % mod * inv[y - a] % mod;
                tmp += (r1 * r2) % mod * 2ll % mod;
            }
            res.push_back(tmp);
        }
    }

    for (auto r : res) {
        cout << r << endl;
    }
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define M 1000000007
#define N 20000

int i, j, k, n, m, t, d;
ll jc[N + 50], inv[N + 50], res;

ll su(ll a, ll b) {
    a += b;
    return (a >= M) ? a - M : a;
}

ll ksm(ll a, ll p) {
    ll res = 1;
    while (p) {
        if (p & 1) {
            res = res * a % M;
        }
        a = a * a % M;
        p >>= 1;
    }
    return res;
}

ll c(ll n, ll m) {
    if (n < m || n < 0 || m < 0) {
        return 0;
    }
    return jc[n] * inv[m] % M * inv[n - m] % M;
}

ll fuck(ll n1, ll m1, ll n2, ll m2) {
    return c(m1 - 1, n1 - 1) * c(m2 - 1, n2 - 1) % M;
}

void solve() {
    ios::sync_with_stdio(0);
    jc[0] = inv[0] = 1;
    for (i = 1; i <= N; i++) {
        jc[i] = jc[i - 1] * i % M;
    }
    inv[N] = ksm(jc[N], M - 2);
    for (i = N - 1; i >= 1; i--) {
        inv[i] = inv[i + 1] * (i + 1) % M;
    }
    
    cin >> n >> m;
    for (i = 1; i <= n + m; i++) {
        j = i / 2; 
        k = i - j;
        cout << (fuck(j, n, k, m) + fuck(k, n, j, m)) % M << endl;
    }
}